//数据结构--时间复杂度
//时间复杂度按消耗的时间：O(1) < O(logn) < O(n) < O(nlogN) < O(n^2) < O(n^3) < O(n^k) < O(2^n) <O(n!)

public class DataStructComplexity{
    //编写一个main的主方法
    public static void main(String[] args){

        int n = 10; 

        /**
         * 1. 常数阶 O(1)的时间复杂度
         * 这种与问题规模的大小无关（n的多少），执行时间恒定的算法，我们称之为具有O(1)的时间复杂度，又叫常数阶。
        */
        int sum = 0;       /*执行一次*/
        sum = (1 + n) * n / 2;      /*执行一次*/
        System.out.println( "常数阶 : "+ sum);           /*执行一次*/


        /**
         * 2. 对数阶 时间复杂度为O(log2(n))
         * 由于每次count乘以2之后，就距离n更近了一分。 也就是说，有多少个2相乘后大于n，则会退出循环。 
         * 由2^x=n 得到x=log2(n)。 所以这个循环的时间复杂度为O(log2(n))。
        */
        int count = 1;  
        int sum2 = 0;    
        while (count < n){
            count = count * 2;
            /*时间复杂度为O(1)的程序步骤序列*/
            sum2 +=count;
        }
        System.out.println( "对数阶 : "+ sum2); 



        /**
         * 3. 线性阶 时间复杂度为O(n)
         * 线性阶的循环结构会复杂很多。要确定某个算法的阶次，我们常常需要确定某个特定语句或某个语句集运行的次数。因此，我们要分析算法的复杂度，关键就是要分析循环结构的运行情况。
         * 下面这段代码，它的循环的时间复杂度为O(n)， 因为循环体中的代码须要执行n次。
        */

        int sum3 = 0;    
        for(int i = 0; i < n; i++){
            /*时间复杂度为O(1)的程序步骤序列*/
            sum3 +=i;
            
        }
        System.out.println( "线性阶 : "+ sum3); 

        /**
         * 4. 线性对数阶 时间复杂度 O(nlogn)
         * 将对数阶循环了n次，n*O(logn)，时间复杂度就是O(nlogn)。
        */
        int sum4 = 0;  
        for(int i = 0; i < n; i++){
            int j = 1;
            while(j < n){
                j = j * 2;
                sum4 +=j;
            }
        }
        System.out.println( "线性对数阶 : "+ sum4); 


        /**
         * 5. 平方阶 时间复杂度为O(n^2)
        */
        int i, j;   
        int sum5 = 0;   
        for(i = 0; i < n; i++){
            for(j = 0; j < n; j++){
                /*时间复杂度为O(1)的程序步骤序列*/
                sum5 += j;
            }
        }
        System.out.println( "平方阶 : "+ sum5); 




    }

}
